package lanqiao.demo;

import java.math.BigInteger;
import java.util.Scanner;

public class Test5 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        BigInteger res = BigInteger.ZERO;
        for (int i = 0; i <= n; i++) {
            res = res.add(new BigInteger(i+"").pow(8));
        }
        res = res.mod(new BigInteger("123456789"));
        System.out.println(res);
    }
}
